public class WidthOfBinaryTree {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public int widthOfBinaryTree(TreeNode root) {
        TreeNode[] qnode = new TreeNode[3001];
        int[] qindex = new int[3001];
        int l=0,r=0;
        qnode[r] = root;
        qindex[r++] = 1;
        int width = 1;
        while(l < r){
            int size = r-l;

            width = Math.max(width,qindex[r-1] - qindex[l] + 1);
            for(int i = 0; i < size; i++ ) {
                TreeNode node = qnode[l];
                if(node.left != null) {
                    qnode[r] = node.left;
                    qindex[r++] = qindex[l]*2;
                }

                if(node.right != null) {
                    qnode[r] = node.right;
                    qindex[r++] = qindex[l]*2+1;
                }
                l++;
            }

        }
        return width;
    }
}
